Extensible Tokens
Problem description
A scanner recognizes various tokens and performs various actions on them.
In this project, design the implementation of tokens such that they can
be augmented without changing the existing code. In other words,
write a reuseable token representation so that other people can extend
it without having to make any change in the base code.
For example, one may start with tokens such as Identifier and
Number. Each type of tokens have its own operations such as
GetType or Print. Then someone may later want to support
a new type of tokens, for example, BinaryInt such as x10001.
In addition, someone else may want to add a new function to process
all tokens, for instance, Count, which counts the number of tokens
of each type. The question is how you can design the representation
of tokens so that later additions can be easily added. The specific
requirements are as follows.
-
The code for basic tokens should be written with no prior knowledge of
later additions. Although it expect extensions, it should not know
the exact name and nature of the new token (e.g. BinaryInt) and
new function (e.g. Count).
-
Adding new tokens and functions should not change any source code for basic
tokens.
-
Any program that uses basic tokens should behave exactly like it does before
the extension. Any program that uses the new tokens should be able
to use the added tokens or functions.
Project organization
-
This project is carried out by a group of preferrably two or at most three
people. Group discussion and group work are part of the intension
of this assignment. Since the assignment and the grading
is the same for both CS254 and CS454, groups can form between members of
both classes.
-
Turn in a written report and an implementation for grading.
-
(40 out of 100 points) A written report on the design of extensible tokens,
with the following sections
-
(10 out of 100 points) A design that allows for new tokens to be added
-
(10 out of 100 points) A design that allows for new functions to be added
-
(20 out of 100 points) A design that allows for both new tokens and new
functions to be added
-
(60 out of 100 points) Implementation of the extensible tokens that you
designed in either C++ or Java. Talk to the instructor if you want
to used a different language.
-
(10 out of 100 points) Basic tokens (including Meta, ID, Number, Symbol,
RWord). Turn in a program that scans and prints all basic tokens.
-
(20 out of 100 points) Addition of a new token, BinaryInt, which
is a sequence of 0s and 1s with letter x at the beginning.
An example is x1001. Turn in a program that scans and prints
basic tokens plus BinaryInt.
-
(20 out of 100 points) Addition of a new method for all above token types,
Count, which add 1 to the total count of the corresponding type
of tokens appeared in a program. Turn in a program that scans and counts
basic tokens plus BinaryInt.
-
The basic scanner and the extensions must be implemented by separate
group members.
-
(10 out of 100 points) Turn in a README file. Document implementation-specific
issues such as the language used, the files included, and the partition
of the implementation work among group members.
-
A single grade will be assigned to each group. The grade is the same
for all members in the group.
-
Requirements for the scanner (or the construction of tokens)
-
This project does not require the scanner to be extensible.
You can modify the source code of the scanner to recognize BinaryInt.
-
You can use your previous implementation of the scanner project or the
supplied scanner implementation as a basis.
-
Extra credit. (10 points) Make the scanner extensible.
That is, allow new token recognition be added without changing the source
code of the basic scanner.
Recommended reading
Thinking in C++. Eckel, Prentice Hall, 1995. (Use it as
a C++ reference book, it contains clear explanations and concise examples).
I have a copy of the book that you can borrow for a short period of time
(so that other groups can use it as well).
Design Patterns: Elements of Reusable Object-Oriented Software,
Gamma, Helm, Johnson, and Vlissides, Addision-Wesley, 1995. Read
the section on Visitor pattern, pp. 331-344. I have a copy of the
book that you can borrow for a short period of time (so that other groups
can use it as well).
Synthesizing
Object-Oriented and Functional Design to Promote Re-Use. Krishnamurthi,
Felleisen and Friedman, Technical report TR 98-299, Rice University, 1998.